#include "graph_support/alg_correctness_tests/TestBorderCondition.h"

#include <vector>

#include <boost/bind.hpp>

#include "graph_support/attributes/FlowEdgeAttributes.h"
#include "graph_support/impls/vector/VectorGraph.h"

#include "graph_support/utils/test_my_graph/BoostTestUtils.h"
#include "graph_support/utils/CollectionsInit.h"

#include "graph_support/alg/flow/Dinic.h"
#include "graph_support/alg/traversal/GrTraversalBFS.h"

using namespace GRAPH_SUPPORT_NS::attributes;
using namespace GRAPH_SUPPORT_NS::utils;
using namespace GRAPH_SUPPORT_NS::impls::vector;
using namespace GRAPH_SUPPORT_NS::alg::flow;
using namespace GRAPH_SUPPORT_NS::alg::traversal;

typedef VectorGraphTmpl< int > VGraphI;
typedef VectorGraphTmpl<
		int,
		FlowEdgeAttributesTmpl< double >,
		stdext::hash< int >,
		stdext::equal_to< int >
		> VFlowNetI;

template< typename GraphT, typename AttrsGenFnT >
void makeGraphAlmostFull( GraphT & gr, AttrsGenFnT attrsGenFn )
{
	typedef typename GraphT::VertexIterator VIt;

	VIt stopIt = gr.getVerticesEnd();
	for ( VIt ait = gr.getVerticesBeg(); ait != stopIt; ++ait )
	{
		for ( VIt bit = gr.getVerticesBeg(); bit != stopIt; ++bit )
		{
			if ( ( * ait ) != ( * bit ) )
			{
				gr.addEdge( * ait, * bit, attrsGenFn() );
			}
		}
	}
}

namespace
{
	double get123()
	{
		return 123;
	}

	VGraphI::EdgeAttributes getLength1Attrs()
	{
		return VGraphI::EdgeAttributes();
	}

	void storeEdges( std::vector< VGraphI::GrEdgePtr > & storage, const VGraphI::GrEdgePtr edgePtr )
	{
		storage.push_back( edgePtr );
	}
}

void TestDinicOnFullGraph()
{
	std::vector< int > vertices = arr2vector< int >( ( const int [] ) { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } );
	VFlowNetI gr( vertices, true );
	{
	Dinic< VFlowNetI > dinic( gr );
	dinic( gr.num2vert( 0 ), gr.num2vert( 1 ) );
	BOOST_CHECK_EQUAL( 0, dinic.getTotalFlow() );
	}

	makeGraphAlmostFull( gr, get123 );
	{
	Dinic< VFlowNetI > dinic( gr );
	dinic( gr.num2vert( 0 ), gr.num2vert( 1 ) );
	BOOST_CHECK_LT( 0, dinic.getTotalFlow() );
	}
}

void TestBFSTraversalOnFullGraph()
{
	std::vector< int > vertices = arr2vector< int >( ( const int [] ) { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } );
	VGraphI gr( vertices );
	std::vector< VGraphI::GrEdgePtr > storage;
	GrTraversalBFSAllEdges( gr, gr.num2vert( 0 ), boost::bind( storeEdges, boost::ref( storage ), _1 ) );
	BOOST_CHECK_EQUAL( 0, storage.size() );

	makeGraphAlmostFull( gr, getLength1Attrs );
	GrTraversalBFSAllEdges( gr, gr.num2vert( 0 ), boost::bind( storeEdges, boost::ref( storage ), _1 ) );
	BOOST_CHECK_EQUAL( 9, storage.size() );
}
